package top.fengleifeng.question;

import java.util.LinkedList;
import java.util.List;
import top.fengleifeng.util.Constants;

/**
 * @author : fengelfeing
 * @version V1.0
 * @Project: leetcode-test
 * @Package : top.fengleifeng.question
 * @Description:
 * @Date: 2020年11月02日7:53 下午
 */
public class Num1020飞地的数量 {

    /**
     * 思路：
     */
    class Solution {

        public int numEnclaves(int[][] A) {
            int result = 0;
            for (int i = 0; i < A.length; i++) {
                for (int j = 0; j < A[i].length; j++) {
                    if (A[i][j] == 1) {
                        List<Integer[]> list = new LinkedList<>();
                        boolean[][] booleaned = new boolean[A.length][A[0].length];
                        if (!check(i, j, booleaned, A, list)) {
                            for (int k = 0; k < list.size(); k++) {
                                A[list.get(k)[0]][list.get(k)[1]] = 0;
                            }
                            result = result + list.size();
                        }
                    }
                }
            }
            return result;
        }

        private boolean check(int i, int j, boolean[][] booleaned, int[][] A, List<Integer[]> list) {
            list.add(new Integer[]{i, j});
            booleaned[i][j] = true;
            if (j - 1 < 0 || j + 1 >= A[i].length || i - 1 < 0 || i + 1 >= A.length) {
                return true;
            }
            if (i - 1 >= 0 && A[i - 1][j] == 1 && !booleaned[i - 1][j]) {
                if (check(i - 1, j, booleaned, A, list)) {
                    return true;
                }
            }
            if (i + 1 < A.length && A[i + 1][j] == 1 && !booleaned[i + 1][j]) {
                if (check(i + 1, j, booleaned, A, list)) {
                    return true;
                }
            }
            if (j - 1 >= 0 && A[i][j - 1] == 1 && !booleaned[i][j - 1]) {
                if (check(i, j - 1, booleaned, A, list)) {
                    return true;
                }
            }
            if (j + 1 < A[i].length && A[i][j + 1] == 1 && !booleaned[i][j + 1]) {
                if (check(i, j + 1, booleaned, A, list)) {
                    return true;
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        int[][] ints = {{0, 0, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 0}, {0, 0, 0, 0}};
//        int[][] ints = {{0, 0, 0, 1, 1, 1, 0, 1, 0, 0}, {1, 1, 0, 0, 0, 1, 0, 1, 1, 1}, {0, 0, 0, 1, 1, 1, 0, 1, 0, 0},
//            {0, 1, 1, 0, 0, 0, 1, 0, 1, 0}, {0, 1, 1, 1, 1, 1, 0, 0, 1, 0}, {0, 0, 1, 0, 1, 1, 1, 1, 0, 1},
//            {0, 1, 1, 0, 0, 0, 1, 1, 1, 1}, {0, 0, 1, 0, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 1, 0, 0, 0, 0},
//            {0, 0, 0, 0, 1, 1, 0, 0, 0, 1}};
        Constants.printArrs(ints);
        int i = new Num1020飞地的数量().new Solution().numEnclaves(ints);
        System.out.println(i);
    }
}
